package euler

import (
	"math/big"
	"sort"
)

var PrimeList []int
var TenPower []int = []int{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000}

func init() {
	FillPrime(10000)
}

func IsPrime(n int) bool {
	if n <= 1 {
		return false
	}
	if n%2 == 0 || n%3 == 0 {
		return n == 2 || n == 3
	}
	for x := 6; x*x-2*x+1 <= n; x += 6 {
		if n%(x-1) == 0 || n%(x+1) == 0 {
			return false
		}
	}
	return true
}

func FillPrime(to int) {
	if len(PrimeList) < 2 {
		PrimeList = []int{2, 3}
	}
	x := PrimeList[len(PrimeList)-1]
	if x >= to {
		return
	}
	for x += 2; x <= to; x += 2 {
		if IsPrime(x) {
			PrimeList = append(PrimeList, x)
		}
	}
}

func GetPrime() func() int {
	x := -1
	return func() int {
		x++
		l := len(PrimeList)
		for l <= x {
			FillPrime(2 * PrimeList[len(PrimeList)-1])
			l = len(PrimeList)
		}
		return PrimeList[x]
	}
}
func PrimeDivisors(n int) []int {
	if IsPrime(n) {
		return []int{n}
	}
	result := []int{}
	gp := GetPrime()
	for n > 1 {
		x := gp()
		if n%x == 0 {
			n /= x
			result = append(result, x)
			for n%x == 0 {
				n /= x
			}
		}
		if IsPrime(n) {
			result = append(result, n)
			n = 1
		}
	}
	return result
}

// func Fibonacci() func() int {
// 	a0, a1 := 0, 1
// 	return func() int {
// 		a0, a1 = a1, a0+a1
// 		return a1
// 	}
// }

func Fibonacci() func() *big.Int {
	a0 := big.NewInt(0)
	a1 := big.NewInt(1)
	return func() *big.Int {
		a0, a1 = a1, a0.Add(a0, a1)
		return a1
	}
}

func Factorial(n int64) *big.Int {
	if n == 1 {
		return big.NewInt(1)
	} else {
		ans := big.NewInt(n)
		return ans.Mul(ans, Factorial(n-1))
	}
}

func IsPalindrome(n, base int) bool {
	return n == ReverseNumber(n, base)
}

func IsPalindromeString(s string) bool {
	return s == ReverseString(s)
}

func ReverseNumber(n, base int) int {
	m := 0
	for n > 0 {
		m = m*base + n%base
		n /= base
	}
	return m
}
func ReverseString(s string) string {
	sr1, sr2 := []rune(s), []rune(s)
	l := len(sr1)
	for i, v := range sr1 {
		sr2[l-i-1] = v
	}
	return string(sr2)
}

func GCD[T int | int32 | int64](n, m T) T {
	if n < m {
		return GCD(n, m%n)
	}
	for m != 0 {
		t := n
		n, m = m, t%m
	}
	return n
}

func TriangularNumber() func() int64 {
	var s int64 = 0
	return func() int64 {
		s++
		return (1 + s) * s / 2
	}
}

// 计算正整数的因子个数，不仅限于质数因子
func CountDivisors(n int) int {
	if IsPrime(n) {
		return 2
	}
	if n == 1 {
		return 1
	}
	x, r := 2, 2
	for ; x*x < n; x++ {
		if n%x == 0 {
			r += 2
		}
	}
	if x*x == n {
		r += 1
	}
	return r
}

func CollatzSeqLen(s int) int {
	l := 1
	for s != 1 {
		if s%2 == 0 {
			s /= 2
		} else {
			s = 3*s + 1
		}
		l++
	}
	return l
}

// called by p021 p023
func SumProperDivisors(n int) int {
	if n < 1 {
		panic("Less than 1 in SumProperDivisors().")
	}
	sum, x := 1, 2
	for x*x < n {
		if n%x == 0 {
			sum += x + n/x
		}
		x++
	}
	if x*x == n {
		sum += x
	}
	return sum
}

func IntPow(x, y int) int {
	pow := 1
	for i := 0; i < y; i++ {
		pow *= x
	}
	return pow
}

// Not for int, considering check some string like "0123456" occasionally.
func IsUniqueDigits(ns string) bool {
	bytes := []byte(ns)
	l := len(bytes)
	for i := 0; i < l; i++ {
		for j := i + 1; j < l; j++ {
			if bytes[i] == bytes[j] {
				return false
			}
		}
	}
	return true
}

func IsSymmetric(s string) bool {
	l := len(s)
	for i := 0; i <= l/2; i++ {
		if s[i] != s[l-1-i] {
			return false
		}
	}
	return true
}

func Permutations(k int, input string) []string {
	output := []string{}
	if k == 1 {
		output = append(output, input)
	} else {
		output = Permutations(k-1, input)
		str := []byte(input)
		for i := 0; i < k-1; i++ {
			tmp := str[i]
			str[i] = str[k-1]
			str[k-1] = tmp
			output = append(output, Permutations(k-1, string(str))...)
		}

	}
	return output
}

func IndexOf(f []int, t int) int {
	left, right := 0, len(f)-1
	for left <= right {
		mid := (left + right) / 2
		if f[mid] == t {
			return mid
		} else if f[mid] <= t {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

func InDigits(n int) []int {
	m := ReverseNumber(n, 10)
	result := []int{}
	for m > 0 {
		result = append(result, m%10)
		m /= 10
	}
	return result
}

func CompareInDigits(a, b int) bool {
	ad := InDigits(a)
	bd := InDigits(b)
	sort.Ints(ad)
	sort.Ints(bd)
	if len(ad) != len(bd) {
		return false
	}
	for i := 0; i < len(ad); i++ {
		if ad[i] != bd[i] {
			return false
		}
	}
	return true
}
